package study;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ConcurrentHashMap;

public class SmallestSubsequence {
    public static String smallestSubsequence(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int[] useNum = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0};
        int[] existNum = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0};
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            useNum[charArray[i] - 'a']++;
        }
        StringBuilder sub = new StringBuilder();
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            if (existNum[c - 'a'] == 0) {
                while (sub.length() > 0 && sub.charAt(sub.length() - 1) > c) {
                    if (useNum[sub.charAt(sub.length() - 1) - 'a'] > 0) {
                        existNum[sub.charAt(sub.length() - 1) - 'a'] = 0;
                        sub.deleteCharAt(sub.length() - 1);
                    } else {
                        break;
                    }
                }
                existNum[c - 'a'] = 1;
                sub.append(c);
            }
            useNum[c - 'a'] -= 1;
        }
        return sub.toString();
    }

    //对拍 不会
    public static String smallestSubsequence2(String s) {
        return null;
    }

    public static void main(String[] args) {
        String s = "bcabc";
        String ret1 = smallestSubsequence(s);
       // String ret2 = smallestSubsequence2(s);
        System.out.println(ret1);
       // System.out.println(ret2);
    }
}
